package com.cty._04_Optimization._40_KLeastNumbers;

/**
 * @Auther: cty
 * @Date: 2020/7/16 8:47
 * @Description: 面试题40：最小的k个数
 * 题目：输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8
 * 这8个数字，则最小的4个数字是1、2、3、4。
 * @version: 1.0
 */
public class KLeastNumbers {
    /**
     * 方法一：划分算法实现，修改数组
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * @param array
     * @param length
     * @param k
     */
    public static void kLeastNumbers(int[] array, int length, int k){
        if(array==null || length<k || k<=0)
            return;

        int start = 0;
        int end = length - 1;
        int index = partition(array,length,start,end);
        while(index != k-1){
            if(index > k-1)
                end = index - 1;
            else
                start = index + 1;
            index = partition(array,length,start,end);
        }  // end while

        for (int i = 0; i < k; i++)
            System.out.print(array[i] + " ");
        System.out.println();
    }  // end kLeastNumbers()

    private static int partition(int[] array, int length, int start, int end){
        if(array==null || length<=0 || start<0 || end>=length || end<start)
            return -1;

        int pivotIndex = randomOfRange(start,end);
        int pivot = array[pivotIndex];
        swap(array,pivotIndex,end);

        int leftPtr = start - 1;
        int rightPtr = end;
        while(true){
            while(array[++leftPtr] < pivot);  // 遇到大于等于枢纽值停下
            while(rightPtr>start && array[--rightPtr]>pivot);  // 遇到小于等于枢纽值或start位置停下

            if(leftPtr >= rightPtr)
                break;
            swap(array,leftPtr,rightPtr);
        }  // end while

        swap(array,leftPtr,end);
        return leftPtr;
    }  // end partition()


    private static int randomOfRange(int start, int end){
        return start + (int)(Math.random()*(end-start+1));
    }  // end randomOfRange()

    private static void swap(int[] array, int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

}  // end class
